package code.D1214;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 * author : yeswater
 * date : 2023/12/14
 * 
 * 单词拆分
 * 
 */

public class T139 {
    
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1]; // length + 1 ??  空值在第一个 所以 + 1
        dp[0] = true; // 初始化
        
        // 方便 check
        HashSet<String> set = new HashSet<>(wordDict);
        
        for (int j = 1; j <= s.length(); j++) { // <= 因为前面长度设置为  len + 1
            for (int i = j - 1; i >= 0; i--) {
                dp[j] = dp[i] && set.contains(s.substring(i, j)); // 前面可以  && 后面包含
                if (dp[j]) break;
            }
        }
        return dp[s.length()];
    }
    
    // public boolean check(String s) {
    //     return map.getOrDefault(s, false);
    // }
}
